1. Field of the Invention (Technical Field)
The present invention relates to electronic communications which are anonymous yet cryptographically authenticated.
2. Background Art
Note that the following discussion refers to a number of publications by author(s) and year of publication, and that due to recent publication dates certain publications are not to be considered as prior art vis-a-vis the present invention. Discussion of such publications herein is given for more complete background and is not to be construed as an admission that such publications are prior art for patentability determination purposes.
Introduction
The idea of providing anonymous and authenticated communications at the same time may seem like a contradiction. However, there are many situations in which this is desirable. For example, suppose that a database of information is being compiled where the source of the data must be from a trusted set of users, but at the same time the source does not want their identity linked with the data they contribute (e.g., a collection of financial data). The present invention addresses the issues of anonymous messages and communications together with authentication that the source is to be trusted.
Anonymous Messages
Ensuring that the content of a message does not give clues to the author is a non-cryptographic problem. To create an anonymous message, one could simply avoid including identifying information in the message and leave the message unsigned. There may, however, be other clues within the message to identify the writer such as wording, spelling and grammar errors, or choice of typewritten font. Environmental issues such as group make up, size of group, and how well participants know each other may also be factors to consider. If the members do not know each other, getting rid of slang or spelling errors may not be much of an issue. However, it should be kept in mind that if some user is in the habit of using any sort of unique style, then this may be noticeable and while this may not identify the author per se, if multiple messages contain this common style, it may be assumed (correctly or not) that the messages are by the same author. S. Hayne, et al., Attribution accuracy when using anonymity in group support system, International Journal of Human Computer Studies, v.47, no. 3, pp. 429-452 (1997) and B. Gavish, et al., Anonymous Mechanisms in Group Decision Support Systems Communications, Decision Support Systems, v. 23, no. 4, pp. 297-328 (1998) discuss these issues in more detail. The present discussion concentrates on other design goals that can be achieved cryptographically.
Anonymity and Authentication
In an anonymous environment the sender of a message is unidentifiable. If the users are supposed to be members of a distinguished group, then authentication is necessary to avoid use by non-members. It is also important to guarantee that a message has not been altered since it was sent by an authorized source.
One way to provide authentication is to have all the group members share a common piece of information. Showing knowledge of the information proves valid group membership. For example, the users could share a symmetric encryption/decryption key. When a member wished to send a message to another member, the member would use the key to encrypt the message. The encrypted message would be sent to another group member and if that person could decrypt the message using the shared key, then the receiver would be sure that a valid group member had sent it. Furthermore, the sender of the message would be assured that only a valid group member would be able to decrypt the message. This scheme preserves anonymity: as long as all group members use the same key, no one knows which member encrypted the message. Furthermore it provides data integrity because if a message has been altered since it was sent, it will not decrypt properly.
Although this scheme is simple, there are drawbacks. Group members would have to be trusted not to give the shared secret away to non-group members. If this happened, neither the bad group member nor the unauthorized user who illegitimately obtained the key could be identified. The key would have to be updated whenever a group member left or if the key were suspected of being compromised. The question of key distribution and update can be a serious problem if the group membership is very dynamic or if there is concern of key compromise.
There are several different types of authentication schemes that can preserve anonymity and address more of the issues raised above. For example, S. Schechter, et al., Anonymous Authentication of Membership in Dynamic Groups, Proceedings of Financial Cryptography '99, vol. 1648 LNCS, pp. 184-195 (1999) uses public key cryptography to construct verifiable common secret encoding to prove group membership. In their scheme, dynamic group membership is not an issue. One-time certificates or zero-knowledge proofs are other common methods. A. De Santis, et al., Communication-efficient anonymous group identification, Proceedings of the ACM Conference on Computer and Communications Security, pp. 73-82 (1998); and K. Oish, et al., Anonymous public-key certificates and their applications, IEICE Transactions, vol. E81-A, no. 1, pp. 65-71 (1998). However, these schemes are more complicated than the shared encryption key scheme and the latter involve group interaction.
Anonymity Revocation
In situations where true anonymity exists, the source of information is completely untraceable. This may cause undesirable situations; for example, troublemakers, insiders, and criminals can act without fear of detection. Instead of true anonymity, revocable anonymity may be preferable. In systems providing revocable anonymity, anonymity is in place unless a specified event (e.g., court order) demands it be revoked and the identity of the offender revealed. Key escrow is a common mechanism used to provide revocable anonymity. D. Boneh, et al., Anonymous Authentication with Subset Queries, Proceedings of the 6th ACM conference on Computer and Communications Security, pp. 113-119 (1999) describes an interactive zero-knowledge scheme which supports identity escrow and key revocation (without having to issue new keys). The interactive communication required is logarithmic in the number of users. The system also provides unlinkability and allows users to be categorized into groups/subsets.
Revocable anonymity mitigates abuses by insiders in the system, but at a cost of confidence in true anonymity. The decision of whether or not to revoke anonymity depends on the situation. For example, within a company, employees may desire anonymity when communicating electronically, but the company may have the right to revoke anonymity if wrongdoing is suspected. On the other hand, if a community of competitive companies is contributing information to a joint venture, they may want their communications to be strictly anonymous with no possibility of revocation in order to protect proprietary information. Hence, instead of revocation of anonymity the present invention describes a protocol that enables anonymous message revocation. A bad message can be revoked, but there is no chance that the identity of the sender can be revealed.
Anonymous Communications
Even if the users employ some method to authenticate their messages to each other anonymously, if others are able to view the network communications it may be clear who the communicating parties were and the anonymity controls would be ineffective. Providing anonymous communications has been studied in detail and we just mention some of the methods here. See D. Chaum, Untraceable Electronic Mail, Return Addresses and Digital Pseudonyms, Communications of the ACM, vol. 24, no. 2, pp. 84-88 (1981) for one of the first discussions on the topic.
There are several different mechanisms presently in use to attempt to thwart traffic analysis. The simplest is called a Type 0 remailer. The Type 0 remailer simply strips identifying headers off the e-mail and forwards the message to the intended recipient. The originator's IP address is not revealed to the recipient since it is sent through an intermediate server, however this does not protect against someone who can observe the communication from the sender to the remailer server. Building on the Type 0 remailer is a Type 1 remailer. Here the e-mail message consists of a nested set of encrypted messages (similar to an onion structure) and is sent through a path of specialized re-encrypting routers called mixes. Mixes will only forward a message after receiving N messages (to defeat message tracking). Type 1 remailers are subject to spam attacks, some traffic analysis and replay attacks. A Type 2 remailer, sometimes called a mixmaster, is similar to a Type 1, but prevents traffic analysis and replay, by using padding, delay and reordering. There are several variants on these types of systems including several commercially available products.
Several web sites offer simple “anonymizing” email forwarding, with header removal and/or anonymous name substitution. Some offer anonymous web surfing, such as Anonymizer.com®. Typical sites offer a basic service for free, and upgraded service for a fee. Others are supported by advertising, or are simply operated as a public service.
The Cypherpunks (http://www.csua.berkeley.edu/cypherpunks/Home.html) have a mixmaster (type 2) remailer network with about twenty nodes. Forwarding latency (per hop) ranges from a few minutes to hours. Several sites post hourly latency statistics.
The present invention is of a cryptographic method and system for a group of users to electronically share information in an anonymous, yet authenticated way. However, anonymous communications open the door for undetectable system abuse. This can be dealt with by using revocable anonymity features, but that may be unacceptable for competitive communicating parties since it could reveal their identity. The present invention employs a multi-level communication structure that mitigates system abuse by allowing message revocation, yet retains true anonymity at the highest level.